The invention generally relates to random sequence generators, and more particularly to cellular automaton devices for generating random sequence signals.
Random sequence generators have been used to generate random sequence signals in many applications. For example, they are used for generating random sequence signals in implementing randomized algorithms in computers. They are also used for generating instruction sequences for self-testing of microcontrollers, encryption in smart cards, and dithering in image processing.
A conventional random sequence generator in the form of linear cellular automaton device is schematically illustrated in FIG. 1. FIG. 2 shows an equivalent functional block diagram of the embodiment in FIG. 1. In FIG. 1, a plurality of linear cellular automatons or cells 10 are inter-connected to one another. Each cell 10 may optionally receive a one-bit input 12 from data and address busses and generates a one-bit output 14. Outputs 14 are loaded into an instruction register (not shown) as pseudo-random instruction sequences for use, for example, in self-testing of microcontrollers.
In each cell 10, a storage element 22, such as a flip-flop, stores a current value of output 14 for use to generate a next value of the output and for providing to adjacent cells 10 as input 32. Storage element 22 is connected to an exclusive-OR gate 24 via a control gate 26, which controls whether to allow the current value of output 14 to pass through control gate 26 for inputting to an exclusive-OR gate 24. For example, if control gate 26 has a coefficient kn equal to 1, the current value of output 14 is allowed to pass through the control gate. However, if the coefficient kn is equal to 0, the current value of output 14 cannot pass through control gate 26. The coefficient values (kn, kn+1, kn+2, are determined from a mathematical lookup table which is well known in the art. For example, the coefficients are described in xe2x80x9cMinimal Cost One-Dimensional Linear Hybrid Cellular Automata of Degree Through 500xe2x80x9d, Journal of Electronic Testing: Theory and Applications, 6,255-258 (1995), by Kevin Cattell and Shujian Zhang, the disclosure of which is hereby incorporated by reference.
Exclusive-OR gate 24 receives additional inputs 32 from adjacent cells 10. Inputs 32 are the current output values of adjacent cells 10. All of the inputs at gate 24 are exclusive-ORed and the result is the next value of output 14. Thus, the next value of output 14 is determined based on the combination of its current value, inputs 32 from adjacent cells and optional input 12.
In a specific example shown in FIG. 3, a linear cellular automaton device 40 that comprises a group of 24 cells 10, i.e., having a 24-bit length, is used to generate pseudo-random instruction sequences. In this example, it is assumed that the instruction width is 8 bit and optional inputs 12 are not provided.
Cellular automaton device 40 is organized into three byte sections: byte 1, byte 2 and byte 3, which are inter-connected to one another. Each byte section includes 8 cells 10, which are also inter-connected to one another. Cellular automaton device 40 generates 8-bit output sequences B1, B2 and B3, which may be loaded into an instruction register (not shown). The output sequences B1, B2 and B3 of cellular automaton device 40 are supposed to provide sufficient randomness for use in various applications. However, the randomness of these sequences is very limited, as will be illustrated FIGS. 4A-4C.
FIG. 4A shows that the next state of output B1 for byte 1 is one of two possible states B1-1 and B2-2. The next state of output B1 is determined based on its current state and the input value received from adjacent byte 2, which is either bit 0 or 1, as illustrated in FIG. 3. For example, if the input value from byte 2 is 0, the next state of output B1 is B1-1. On the other hand, if the input value from byte 2 is 1, the next state of output B1 is B1-2. Each of the next possible states B1-1 and B1-2 may have 256 values.
Similarly, FIG. 4B shows that the next state of output B2 for byte 2 is one of four possible states B2-1, B2-2, B2-3 and B2-4. FIG. 4C shows that the next state of output B3 for byte 3 is one of two possible states B3-1 and B3-2.
As can be seen from the above, only a limited number of states can be generated by cellular automaton-device 40 due to the insufficient connections between the byte sections. As a result, the sequences generated do not provide sufficient randomness such that use of these sequences will inevitably result in inefficiencies and errors and could even cause serious security problems if used for encryption purposes.
Another conventional random sequence generator with similar problems is described in U.S. Pat. No. 4,691,291 issued to Wolfram on Sep. 1, 1987, which is hereby incorporated by reference.
Thus, there is a need for a random sequence generator that can generate a large number of states that provide sufficient randomness for a variety of applications.
The present invention provides a random sequence generator for generating an output signal having random values. The generator comprises a plurality of cells inter-connected to one another such that each cell receives, as an input, an output from each cell connected thereto and generates a cell output based on a current value of the cell output and each cell output received. The plurality of cells include k subsets each subset including n cells. A pre-selected cell from each of the k subsets generates an output and the output of the k pre-selected cells is provided as the output signal of the generator. In a specific embodiment, each of the cells is a linear cellular automaton, with k being an instruction width and k*n being an instruction length.
The invention is particularly suitable for internal self-testing of a micrbcontroller in a smart card. This eliminates the need for external test contacts and thus prevents potential break-ins through the external contacts.
The invention also provides a method for generating an output signal having random values from a plurality of inter-connected cells. The method comprises the steps of: (a) arranging the plurality of cells in k subsets, each subset including n cells; (b) applying to each of the cells, as an input, an output from each cell connected thereto; (c) generating a cell output from each of the cells based on a current value of the cell output and each cell output received; (d) extracting an output from a pre-selected cell of each of the k subsets; and (e) providing the output of the k pre-selected cells as the output signal.
By using the present invention, a huge number of sequences can be generated, thus providing tremendous amount of randomness for a wide range of applications.
Other objects and attainments together with a fuller understanding of the invention will become apparent and appreciated by referring to the following description and claims taken in conjunction with the accompanying drawings.